{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #First Completely Painted Row or Column"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: firstCompleteIndex"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出叠涂元素"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>arr</code> 和一个 <code>m x n</code> 的整数 <strong>矩阵</strong> <code>mat</code> 。<code>arr</code> 和 <code>mat</code> 都包含范围 <code>[1，m * n]</code> 内的 <strong>所有</strong> 整数。</p>\n",
    "\n",
    "<p>从下标 <code>0</code> 开始遍历 <code>arr</code> 中的每个下标 <code>i</code> ，并将包含整数 <code>arr[i]</code> 的 <code>mat</code> 单元格涂色。</p>\n",
    "\n",
    "<p>请你找出 <code>arr</code> 中第一个使得&nbsp;<code>mat</code> 的某一行或某一列都被涂色的元素，并返回其下标 <code>i</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"image explanation for example 1\" src=\"https://assets.leetcode.com/uploads/2023/01/18/grid1.jpg\" style=\"width: 321px; height: 81px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,3,4,2], mat = [[1,4],[2,3]]\n",
    "<strong>输出：</strong>2\n",
    "<strong>解释：</strong>遍历如上图所示，arr[2] 在矩阵中的第一行或第二列上都被涂色。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"image explanation for example 2\" src=\"https://assets.leetcode.com/uploads/2023/01/18/grid2.jpg\" style=\"width: 601px; height: 121px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>遍历如上图所示，arr[3] 在矩阵中的第二列上都被涂色。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == mat.length</code></li>\n",
    "\t<li><code>n = mat[i].length</code></li>\n",
    "\t<li><code>arr.length == m * n</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= m * n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= arr[i], mat[r][c] &lt;= m * n</code></li>\n",
    "\t<li><code>arr</code> 中的所有整数 <strong>互不相同</strong></li>\n",
    "\t<li><code>mat</code> 中的所有整数 <strong>互不相同</strong></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [first-completely-painted-row-or-column](https://leetcode.cn/problems/first-completely-painted-row-or-column/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [first-completely-painted-row-or-column](https://leetcode.cn/problems/first-completely-painted-row-or-column/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3,4,2]\\n[[1,4],[2,3]]', '[2,8,7,4,1,3,5,6,9]\\n[[3,2,5],[1,4,6],[8,7,9]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "      n = len(arr)\n",
    "      r, c = len(mat), len(mat[0])\n",
    "      rowpos = [0] * (n + 1)\n",
    "      colpos = [0] * (n + 1)\n",
    "      rownum = [c] * r\n",
    "      colnum = [r] * c\n",
    "      for i in range(r):\n",
    "        for j in range(c):\n",
    "          k = mat[i][j]\n",
    "          rowpos[k] = i\n",
    "          colpos[k] = j\n",
    "      # print(rowpos)\n",
    "      # print(colpos)\n",
    "      for i in range(n):\n",
    "        k = arr[i]\n",
    "        rownum[rowpos[k]] -= 1\n",
    "        colnum[colpos[k]] -= 1\n",
    "        if rownum[rowpos[k]] == 0 or colnum[colpos[k]] == 0:\n",
    "          return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        r, c = [0] * (m * n + 1), [0] * (m * n + 1)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x = mat[i][j]\n",
    "                r[x] = i\n",
    "                c[x] = j\n",
    "        rows = [0] * m\n",
    "        cols = [0] * n\n",
    "        for i, x in enumerate(arr):\n",
    "            rows[r[x]] += 1\n",
    "            if rows[r[x]] == n:\n",
    "                return i\n",
    "            cols[c[x]] += 1\n",
    "            if cols[c[x]] == m:\n",
    "                return i\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        rcnt = [0] * m\n",
    "        ccnt = [0] * n\n",
    "        pos = [0] * (m * n + 1)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pos[mat[i][j]] = (i, j)\n",
    "        for i, x in enumerate(arr):\n",
    "            r, c = pos[x]\n",
    "            rcnt[r] += 1\n",
    "            ccnt[c] += 1\n",
    "            if rcnt[r] == n or ccnt[c] == m:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        pos = [0] * (m * n + 1)\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                pos[x] = (i, j)\n",
    "        row_cnt = [0] * m\n",
    "        col_cnt = [0] * n\n",
    "        for i, x in enumerate(arr):\n",
    "            r, c = pos[x]\n",
    "            row_cnt[r] += 1\n",
    "            col_cnt[c] += 1\n",
    "            if row_cnt[r] == n or col_cnt[c] == m:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        pos = [0] * (m * n + 1)\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                pos[x] = (i, j)\n",
    "        row_cnt = [0] * m\n",
    "        col_cnt = [0] * n\n",
    "        for i, x in enumerate(arr):\n",
    "            r, c = pos[x]\n",
    "            row_cnt[r] += 1\n",
    "            col_cnt[c] += 1\n",
    "            if row_cnt[r] == n or col_cnt[c] == m:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        \n",
    "        m,n = len(mat),len(mat[0])\n",
    "        pos=[0]*(m*n+1)\n",
    "        for i, row in enumerate(mat):\n",
    "            for j,x in enumerate(row):\n",
    "                pos[x] = (i,j)\n",
    "\n",
    "        row_cnt=[0]*m\n",
    "        col_cnt = [0]*n\n",
    "\n",
    "        for k,x in enumerate(arr):\n",
    "            i,j = pos[x]\n",
    "            row_cnt[i]+=1\n",
    "            col_cnt[j]+=1\n",
    "            if row_cnt[i]==n or col_cnt[j]==m:\n",
    "                return k\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        n=len(mat)\n",
    "        m=len(mat[0])\n",
    "        pos=[0]*(m*n+1)\n",
    "        for i,row in enumerate(mat):\n",
    "            for j,x in enumerate(row):\n",
    "                pos[x]=(i,j)\n",
    "        row_cnt=[0]*n\n",
    "        col_cnt=[0]*m\n",
    "        for idx,val in enumerate(arr):\n",
    "            y,x=pos[val]\n",
    "            row_cnt[y]+=1\n",
    "            col_cnt[x]+=1\n",
    "            if row_cnt[y]==m or col_cnt[x]==n:\n",
    "                return idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        pow = [0] * (m * n + 1)\n",
    "        row_list = [0] * m\n",
    "        col_list = [0] * n\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, vaule in enumerate(row):\n",
    "                pow[vaule] = (i, j)\n",
    "\n",
    "        for i, em in enumerate(arr):\n",
    "            r, c = pow[em]\n",
    "            row_list[r] += 1\n",
    "            col_list[c] += 1\n",
    "            if row_list[r] == n or col_list[c] == m:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        pos = [0] * (m * n + 1)\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                pos[x] = (i, j)\n",
    "        row_cnt = [0] * m\n",
    "        col_cnt = [0] * n\n",
    "        for i, x in enumerate(arr):\n",
    "            r, c = pos[x]\n",
    "            row_cnt[r] += 1\n",
    "            col_cnt[c] += 1\n",
    "            if row_cnt[r] == n or col_cnt[c] == m:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        pos = [0] * (m*n+1)\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                pos[x] = (i,j)\n",
    "        row_cnt = [0] * m\n",
    "        col_cnt = [0] * n\n",
    "        for i, x in enumerate(arr):\n",
    "          r, c = pos[x]\n",
    "          row_cnt[r] += 1\n",
    "          col_cnt[c] += 1\n",
    "          if row_cnt[r] == n or col_cnt[c] == m:\n",
    "            return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        d = [0] * (m * n + 1)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                d[mat[i][j]] = (i, j)\n",
    "        row = [0] * n\n",
    "        col = [0] * m\n",
    "        for i, a in enumerate(arr):\n",
    "            r, c = d[a]\n",
    "            row[r] += 1\n",
    "            if row[r] == m:\n",
    "                return i\n",
    "            col[c] += 1\n",
    "            if col[c] == n:\n",
    "                return i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        d = [0] * (m * n + 1)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                d[mat[i][j]] = (i, j)\n",
    "        row = [0] * n\n",
    "        col = [0] * m\n",
    "        print(n, m)\n",
    "        for i, a in enumerate(arr):\n",
    "            r, c = d[a]\n",
    "            row[r] += 1\n",
    "            if row[r] == m:\n",
    "                return i\n",
    "            col[c] += 1\n",
    "            if col[c] == n:\n",
    "                return i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        pos = [0] * (m * n + 1)\n",
    "\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                pos[x] = (i,j)\n",
    "        \n",
    "        row_cnt = [0] * m\n",
    "        col_cnt = [0] * n\n",
    "\n",
    "        for i, x in enumerate(arr):\n",
    "            r, c = pos[x]\n",
    "            row_cnt[r] += 1\n",
    "            col_cnt[c] += 1\n",
    "            if row_cnt[r] == n or col_cnt[c] == m:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        pos = [0] * (m * n + 1)\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                pos[x] = (i, j)\n",
    "        \n",
    "        row_cnt = [0] * m\n",
    "        col_cnt = [0] * n\n",
    "        for i, x in enumerate(arr):\n",
    "            r, c = pos[x]\n",
    "            row_cnt[r] += 1\n",
    "            col_cnt[c] += 1\n",
    "            if row_cnt[r] == n or col_cnt[c] == m:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        pos = [0] * (m*n+1)\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                pos[x] = (i,j)\n",
    "        row_cnt = [0]*m\n",
    "        col_cnt = [0]*n\n",
    "        for i, x in enumerate(arr):\n",
    "            r, c = pos[x]\n",
    "            row_cnt[r] += 1\n",
    "            col_cnt[c] += 1\n",
    "            if row_cnt[r] == n or col_cnt[c] == m:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        pos = [0] * (m * n + 1)\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                pos[x] = (i, j)\n",
    "        row_cnt = [0] * m\n",
    "        col_cnt = [0] * n\n",
    "        for i, x in enumerate(arr):\n",
    "            r, c = pos[x]\n",
    "            row_cnt[r] += 1\n",
    "            col_cnt[c] += 1\n",
    "            if row_cnt[r] == n or col_cnt[c] == m:\n",
    "                return i\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        t = len(arr)\n",
    "        l = [None for i in range(t+1)]\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                l[mat[i][j]] = (i,j)\n",
    "        \n",
    "        r = [0 for i in range(len(mat))]\n",
    "        c = [0 for i in range(len(mat[0]))]\n",
    "        for i in range(len(arr)):\n",
    "            x,y = l[arr[i]]\n",
    "            r[x] += 1\n",
    "            c[y] += 1\n",
    "            # print(r,c)\n",
    "            if r[x] == len(mat[0]) or c[y] == len(mat):\n",
    "                return i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        dic=[None]*(m*n+1)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dic[mat[i][j]]=(i,j)\n",
    "        \n",
    "        cr,cc=[0]*m,[0]*n\n",
    "        for index,i in enumerate(arr):\n",
    "            x,y=dic[i]\n",
    "            cr[x]+=1\n",
    "            cc[y]+=1\n",
    "            if cr[x]==n or cc[y]==m:\n",
    "                return index\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        d = [0] * (m * n + 1)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                d[mat[i][j]] = (i, j)\n",
    "        row = [0] * n\n",
    "        col = [0] * m\n",
    "        for i, a in enumerate(arr):\n",
    "            r, c = d[a]\n",
    "            row[r] += 1\n",
    "            col[c] += 1\n",
    "            if col[c] == n or row[r] == m:\n",
    "                return i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        pos = [0] * (m * n + 1)\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                pos[x] = (i, j)\n",
    "        row_cnt = [0] * m\n",
    "        col_cnt = [0] * n\n",
    "        for i, x in enumerate(arr):\n",
    "            r, c = pos[x]\n",
    "            row_cnt[r] += 1\n",
    "            col_cnt[c] += 1\n",
    "            if row_cnt[r] == n or col_cnt[c] == m:\n",
    "                return i\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        # m, n = len(mat), len(mat[0])\n",
    "        # axis = {}\n",
    "        # for i in range(m):\n",
    "        #     for j in range(n):\n",
    "        #         axis[mat[i][j]] = (i, j)\n",
    "        # row_count = [0] * m\n",
    "        # col_count = [0] * n\n",
    "        # for i, a in enumerate(arr):\n",
    "        #     r, c = axis[a]\n",
    "        #     row_count[r] += 1\n",
    "        #     col_count[c] += 1\n",
    "        #     if row_count[r] == n or col_count[c] == m:\n",
    "        #         return i\n",
    "\n",
    "        # -------------------------------\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        axis = [0] * (m*n+1)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                axis[mat[i][j]] = (i, j)\n",
    "        row_count = [0] * m\n",
    "        col_count = [0] * n\n",
    "        for i, a in enumerate(arr):\n",
    "            r, c = axis[a]\n",
    "            row_count[r] += 1\n",
    "            col_count[c] += 1\n",
    "            if row_count[r] == n or col_count[c] == m:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 预处理位置+统计行列涂色个数\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        pos = [0] * (m * n + 1)\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                pos[x] = (i, j)\n",
    "                \n",
    "        row_cnt = [0] * m\n",
    "        col_cnt = [0] * n\n",
    "        for i, x in enumerate(arr):\n",
    "            r, c = pos[x]\n",
    "            row_cnt[r] += 1\n",
    "            col_cnt[c] += 1\n",
    "            if row_cnt[r] == n or col_cnt[c] == m:\n",
    "                return i\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        pos = [0] * (m * n + 1)\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                pos[x] = (i, j)\n",
    "        row_cnt = [0] * m\n",
    "        col_cnt = [0] * n\n",
    "        for i, x in enumerate(arr):\n",
    "            r, c = pos[x]\n",
    "            row_cnt[r] += 1\n",
    "            col_cnt[c] += 1\n",
    "            if row_cnt[r] == n or col_cnt[c] == m:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        pos = [0] * (m * n + 1)\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                pos[x] = (i, j)\n",
    "        row_cnt = [0] * m\n",
    "        col_cnt = [0] * n\n",
    "        for i, x in enumerate(arr):\n",
    "            r, c = pos[x]\n",
    "            row_cnt[r] += 1\n",
    "            col_cnt[c] += 1\n",
    "            if row_cnt[r] == n or col_cnt[c] == m:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m=len(mat)\n",
    "        n=len(mat[0])\n",
    "        #标记\n",
    "        row=[0]*m\n",
    "        col=[0]*n\n",
    "        #预记录\n",
    "        s=[0]*(m*n+1)\n",
    "        for i,f in enumerate(mat) :\n",
    "            for j,x in enumerate(f) :\n",
    "                s[x]=(i,j)\n",
    "        for i,x in enumerate(arr) :\n",
    "            a,b=s[x]\n",
    "            row[a]+=1\n",
    "            col[b]+=1\n",
    "            if row[a]==n or col[b]==m :\n",
    "                return i\n",
    "        return 0\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        pos = [0] * (m * n + 1)\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                pos[x] = (i, j)\n",
    "        row_cnt = [0] * m\n",
    "        col_cnt = [0] * n\n",
    "        for i, x in enumerate(arr):\n",
    "            r, c = pos[x]\n",
    "            row_cnt[r] += 1\n",
    "            col_cnt[c] += 1\n",
    "            if row_cnt[r] == n or col_cnt[c] == m:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        pos = [0] * (m * n + 1)\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                pos[x] = (i, j)\n",
    "        row_cnt = [0] * m\n",
    "        col_cnt = [0] * n\n",
    "        for i, x in enumerate(arr):\n",
    "            r, c = pos[x]\n",
    "            row_cnt[r] += 1\n",
    "            col_cnt[c] += 1\n",
    "            if row_cnt[r] == n or col_cnt[c] == m:\n",
    "                return i\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        pos = [None for _ in range(len(mat) * len(mat[0]) + 1)]\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                pos[mat[i][j]] = [i, j]\n",
    "        alreadyRow, alreadyColumn = [len(mat[0]) for _ in range(len(mat))], [len(mat) for _ in range(len(mat[0]))]\n",
    "        for i in range(len(arr)):\n",
    "            alreadyRow[pos[arr[i]][0]] -= 1\n",
    "            alreadyColumn[pos[arr[i]][1]] -= 1\n",
    "            if alreadyRow[pos[arr[i]][0]] * alreadyColumn[pos[arr[i]][1]] == 0:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m=len(mat)\n",
    "        n=len(mat[0])\n",
    "        r=[n]*m\n",
    "        c=[m]*n\n",
    "        s=[[0]*2 for _ in range(m*n)]\n",
    "        for i,x in enumerate(mat):\n",
    "            for j,y in enumerate(x):\n",
    "                s[y-1]=[i,j]\n",
    "        for i,x in enumerate(arr):\n",
    "            r[s[x-1][0]]-=1\n",
    "            c[s[x-1][1]]-=1\n",
    "            if r[s[x-1][0]]==0 or c[s[x-1][1]]==0:\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        tot=len(arr)\n",
    "        pos=[[0]*2 for _ in range(tot+1)]\n",
    "        m,n=len(mat),len(mat[0])\n",
    "        row=[n]*m\n",
    "        col=[m]*n\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pos[mat[i][j]]=[i,j]\n",
    "        for i,num in enumerate(arr):\n",
    "            x=pos[num][0]\n",
    "            y=pos[num][1]\n",
    "            row[x] -=1\n",
    "            col[y] -=1\n",
    "            if row[x]==0 or col[y]==0:\n",
    "                return i\n",
    "        return 12"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        n = len(mat[0])\n",
    "        m = len(mat)\n",
    "        num_index = [[0,0] for i in range(m*n+1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                num_index[mat[i][j]][0] = i\n",
    "                num_index[mat[i][j]][1] = j\n",
    "        num_raw = [n]*m\n",
    "        num_col = [m]*n\n",
    "        for i in range(0,m*n):\n",
    "            num_raw[num_index[arr[i]][0]] -=1\n",
    "            num_col[num_index[arr[i]][1]] -=1\n",
    "            if num_raw[num_index[arr[i]][0]]==0 or num_col[num_index[arr[i]][1]]==0:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        n = len(mat[0])\n",
    "        m = len(mat)\n",
    "        num_index = [[0,0] for i in range(m*n+1)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                num_index[mat[i][j]][0] = i\n",
    "                num_index[mat[i][j]][1] = j\n",
    "        num_raw = [n]*m\n",
    "        num_col = [m]*n\n",
    "        for i in range(0,m*n):\n",
    "            num_raw[num_index[arr[i]][0]] -=1\n",
    "            num_col[num_index[arr[i]][1]] -=1\n",
    "            if num_raw[num_index[arr[i]][0]]==0 or num_col[num_index[arr[i]][1]]==0:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        n,m = len(mat),len(mat[0])\n",
    "        po = [[]for i in range(n*m+1)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                po[mat[i][j]]=[i,j]\n",
    "        cntr,cntc=[0]*(n+1),[0]*(m+1)\n",
    "        for i,v in enumerate(arr):\n",
    "            r,c=po[v][0],po[v][1]\n",
    "            cntr[r]+=1\n",
    "            cntc[c]+=1\n",
    "            if cntr[r] == m or cntc[c] == n:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        d = [0] * (m * n + 1)\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                d[mat[i][j]] = (i, j)\n",
    "        row = Counter()\n",
    "        col = Counter()\n",
    "        print(n, m)\n",
    "        for i, a in enumerate(arr):\n",
    "            r, c = d[a]\n",
    "            row[r] += 1\n",
    "            if row[r] == m:\n",
    "                return i\n",
    "            col[c] += 1\n",
    "            if col[c] == n:\n",
    "                return i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        pos = dict()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                pos[mat[i][j]] = i * n + j\n",
    "        rows = [n] * m\n",
    "        cols = [m] * n\n",
    "        for i, v in enumerate(arr):\n",
    "            p = pos[v]\n",
    "            x, y = p // n, p % n\n",
    "            rows[x] -= 1\n",
    "            cols[y] -= 1\n",
    "            if rows[x] == 0 or cols[y] == 0:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "      m,n=len(mat),len(mat[0])\n",
    "      #x=[n]*m\n",
    "      #y=[m]*n\n",
    "      ans=m*n\n",
    "      d=dict()\n",
    "      for i,a in enumerate(arr):\n",
    "        d[a]=i\n",
    "      for i in range(m):\n",
    "        for j in range(n):\n",
    "          mat[i][j]=d[mat[i][j]]\n",
    "      for i in range(m):\n",
    "        ans=min(ans,max(mat[i]))\n",
    "      for j in range(n):\n",
    "        ans=min(ans,max(mat[i][j] for i in range(m)))\n",
    "      return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        dic = {arr[i]:i for i in range(len(arr))}\n",
    "        r,c = len(mat),len(mat[0])\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                mat[i][j] = dic[mat[i][j]]\n",
    "        matT = [list(i) for i in zip(*mat)]\n",
    "        ans1 = min(max(i) for i in mat)\n",
    "        ans2 = min(max(i) for i in matT)\n",
    "        return min(ans1,ans2)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        idx = {}\n",
    "        for i in range(len(arr)):\n",
    "            idx[arr[i]] = i\n",
    "        matT = [[mat[i][j] for i in range(m)] for j in range(n)]\n",
    "        row = [max([idx[x] for x in mat[i]]) for i in range(m)]\n",
    "        col = [max([idx[x] for x in matT[i]]) for i in range(n)]\n",
    "        _min = m*n\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                _min = min(_min, min(row[i], col[j]))\n",
    "        return _min"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        n, m = len(mat), len(mat[0])\n",
    "        location = [[] for _ in range(n * m + 1)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                location[mat[i][j]] = [i, j]\n",
    "        rowCnt = defaultdict(int)\n",
    "        colCnt = defaultdict(int)\n",
    "        for i in range(len(arr)):\n",
    "            r, c = location[arr[i]][0], location[arr[i]][1]\n",
    "            rowCnt[r] += 1\n",
    "            colCnt[c] += 1\n",
    "            if rowCnt[r] == m or colCnt[c] == n:\n",
    "                return i\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        dict1 = dict()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dict1[mat[i][j]] = (i,j)\n",
    "        row = {}\n",
    "        col = {}\n",
    "        for index,per in enumerate(arr):\n",
    "            x,y = dict1[per]\n",
    "            row[x] = row.get(x,0) + 1\n",
    "            col[y] = col.get(y,0) + 1\n",
    "            if row[x] == n or col[y] == m:\n",
    "                return index\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        pos = {}\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, x in enumerate(row):\n",
    "                pos[x] = (i, j)\n",
    "        row_cnt = {}\n",
    "        col_cnt = {}\n",
    "        for i, x in enumerate(arr):\n",
    "            r, c = pos[x]\n",
    "            row_cnt[r] = row_cnt.get(r, 0) + 1\n",
    "            col_cnt[c] = col_cnt.get(c, 0) + 1\n",
    "            if row_cnt[r] == n or col_cnt[c] == m:\n",
    "                return i\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        axis = {}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                axis[mat[i][j]] = (i, j)\n",
    "        row_count = [0] * m\n",
    "        col_count = [0] * n\n",
    "        for i, a in enumerate(arr):\n",
    "            r, c = axis[a]\n",
    "            row_count[r] += 1\n",
    "            col_count[c] += 1\n",
    "            if row_count[r] == n or col_count[c] == m:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        row_count = [0] * m\n",
    "        col_count = [0] * n\n",
    "        num_to_pos = {}\n",
    "\n",
    "        for row in range(m):\n",
    "            for col in range(n):\n",
    "                num_to_pos[mat[row][col]] = (row, col)\n",
    "\n",
    "        for i, num in enumerate(arr):\n",
    "            row_index, col_index = num_to_pos[num]\n",
    "            row_count[row_index] += 1\n",
    "            col_count[col_index] += 1\n",
    "\n",
    "            if row_count[row_index] == n or col_count[col_index] == m:\n",
    "                return i\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n, dct = len(mat), len(mat[0]), defaultdict(tuple)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dct[mat[i][j]] = (i, j)\n",
    "        row, col = [0] * m, [0] * n\n",
    "        for i, a in enumerate(arr):\n",
    "            r, c = dct[a]\n",
    "            row[r] += 1\n",
    "            col[c] += 1\n",
    "            if row[r] == n or col[c] == m:\n",
    "                return i\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        n=len(mat)\n",
    "        m=len(mat[0])\n",
    "        sign={}\n",
    "        row=[0]*n\n",
    "        col=[0]*m\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                sign[mat[i][j]]=(i,j)\n",
    "        for index,i in enumerate(arr):\n",
    "            a=sign[i]\n",
    "            row[a[0]]+=1\n",
    "            col[a[1]]+=1\n",
    "            if row[a[0]]==m or col[a[1]]==n:\n",
    "                return index\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        col = [0]*n\n",
    "        row = [0]*m\n",
    "        d = dict()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                d[mat[i][j]] = (i, j)\n",
    "        for x, a in enumerate(arr):\n",
    "            i, j = d[a]\n",
    "            row[i] += 1\n",
    "            col[j] += 1\n",
    "            if row[i] == n or col[j] == m:\n",
    "                return x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        matidx = dict()\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        row = [0] * m\n",
    "        col = [0] * n\n",
    "        for i in  range(m):\n",
    "            for j in range(n):\n",
    "                matidx[mat[i][j]] = (i,  j)\n",
    "        for i, num in enumerate(arr):\n",
    "            r, c = matidx[num]\n",
    "            row[r] += 1\n",
    "            col[c] += 1\n",
    "            if row[r] == n or col[c] == m:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        d = dict()\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                d[mat[i][j]] = (i, j)\n",
    "        rows = [0] * m\n",
    "        cols = [0] * n\n",
    "        for i in range(len(arr)):\n",
    "            x, y = d[arr[i]]\n",
    "            rows[x] += 1\n",
    "            if rows[x] == n:\n",
    "                return i\n",
    "            cols[y] += 1\n",
    "            if cols[y] == m:\n",
    "                return i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "\n",
    "        mp = {}\n",
    "\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[0])):\n",
    "                mp[mat[i][j]] = (i, j)\n",
    "        row = [0] * len(mat)\n",
    "        col = [0] * len(mat[0])\n",
    "        for i in range(len(arr)):\n",
    "            ii, jj = mp[arr[i]]\n",
    "            row[ii] += 1\n",
    "            col[jj] += 1\n",
    "\n",
    "            if row[ii] == len(mat[0]) or col[jj] == len(mat):\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        mapping = {}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                mapping[mat[i][j]] = (i,j)\n",
    "        rowMp = {}\n",
    "        colMp = {}\n",
    "        for k in range(m*n):\n",
    "            i, j = mapping[arr[k]]\n",
    "            if(i not in rowMp):\n",
    "                rowMp[i] = 1\n",
    "            else:\n",
    "                rowMp[i] += 1\n",
    "            if(rowMp[i] == n):\n",
    "                return k\n",
    "\n",
    "            if(j not in colMp):\n",
    "                colMp[j] = 1\n",
    "            else:\n",
    "                colMp[j] += 1\n",
    "            if(colMp[j] == m):\n",
    "                return k\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        d = dict()\n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                d[mat[i][j]] = (i, j)\n",
    "        row = Counter()\n",
    "        col = Counter()\n",
    "        for i, a in enumerate(arr):\n",
    "            r, c = d[a]\n",
    "            row[r] += 1\n",
    "            if row[r] == m:\n",
    "                return i\n",
    "            col[c] += 1\n",
    "            if col[c] == n:\n",
    "                return i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        hashtable = dict()\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                hashtable[mat[i][j]] = (i, j)\n",
    "        t = m * n\n",
    "        mjudge = [0 for i in range(m)]\n",
    "        njudge = [0 for i in range(n)]\n",
    "        for some in range(t):\n",
    "            i, j = hashtable[arr[some]]\n",
    "            mjudge[i] += 1\n",
    "            njudge[j] += 1\n",
    "            if mjudge[i] == n or njudge[j] == m:\n",
    "                return some\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        dic = defaultdict(tuple)\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dic[mat[i][j]]= (i,j)\n",
    "        row = [0] * m\n",
    "        col = [0] * n\n",
    "        for i, a in enumerate(arr):\n",
    "            r, c = dic[a]\n",
    "            row[r] += 1\n",
    "            col[c] += 1\n",
    "            if row[r] == n or col[c] == m:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        mapping = {}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                mapping[mat[i][j]] = (i,j)\n",
    "        rowMp = {}\n",
    "        colMp = {}\n",
    "        for k in range(m*n):\n",
    "            i, j = mapping[arr[k]]\n",
    "            if(i not in rowMp):\n",
    "                rowMp[i] = 1\n",
    "            else:\n",
    "                rowMp[i] += 1\n",
    "            if(rowMp[i] == n):\n",
    "                return k\n",
    "\n",
    "            if(j not in colMp):\n",
    "                colMp[j] = 1\n",
    "            else:\n",
    "                colMp[j] += 1\n",
    "            if(colMp[j] == m):\n",
    "                return k\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        d = dict()\n",
    "        n = len(mat)\n",
    "        m = len(mat[0])\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                d[mat[i][j]] = (i, j)\n",
    "        row = Counter()\n",
    "        col = Counter()\n",
    "        print(n, m)\n",
    "        for i, a in enumerate(arr):\n",
    "            r, c = d[a]\n",
    "            row[r] += 1\n",
    "            if row[r] == m:\n",
    "                return i\n",
    "            col[c] += 1\n",
    "            if col[c] == n:\n",
    "                return i\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        col_map = defaultdict(int)  # 列，长度等于m时该列填满\n",
    "        row_map = defaultdict(int)  # 行，长度等于n时该行填满\n",
    "        val_map = dict()\n",
    "        for m in range(len(mat)):\n",
    "            for n in range(len(mat[m])):\n",
    "                val = mat[m][n]\n",
    "                val_map[val] = (m, n)\n",
    "        row_num = len(mat)\n",
    "        col_num = len(mat[0])\n",
    "        for idx, val in enumerate(arr):\n",
    "            m, n = val_map[val]\n",
    "            col_map[n] += 1\n",
    "            row_map[m] += 1\n",
    "            if col_map[n] == row_num or row_map[m] == col_num:\n",
    "                return idx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import *\n",
    "from heapq import *\n",
    "from sys import *\n",
    "from math import *\n",
    "from itertools import *\n",
    "from functools import *\n",
    "from string import *\n",
    "from bisect import *\n",
    "from graphlib import *\n",
    "from sortedcontainers import *\n",
    "from copy import *\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        dct = {}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dct[mat[i][j]] = (i, j)\n",
    "        c, r = Counter(), Counter()\n",
    "        for idx, x in enumerate(arr):\n",
    "            i, j = dct[x]\n",
    "            c[i] += 1\n",
    "            r[j] += 1\n",
    "            if c[i] == n or r[j] == m: return idx\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        book = {mat[i][j]: (i, j) for i, j in product(range(m), range(n))}\n",
    "        rows = [0] * m\n",
    "        cols = [0] * n\n",
    "        for i, (x, y) in enumerate(map(book.__getitem__, arr)):\n",
    "            rows[x] += 1\n",
    "            cols[y] += 1\n",
    "            if rows[x] == n or cols[y] == m:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        row_count = [0] * m\n",
    "        col_count = [0] * n\n",
    "        num_to_position = {}\n",
    "\n",
    "        for row in range(m):\n",
    "            for col in range(n):\n",
    "                num_to_position[mat[row][col]] = (row, col)\n",
    "\n",
    "        for i, num in enumerate(arr):\n",
    "            row_index, col_index = num_to_position[num]\n",
    "            row_count[row_index] += 1\n",
    "            col_count[col_index] += 1\n",
    "\n",
    "            if row_count[row_index] == n or col_count[col_index] == m:\n",
    "                return i\n",
    "\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m,n=len(mat), len(mat[0])\n",
    "        mlefts = [n]*m\n",
    "        nlefts = [m]*n\n",
    "        v2pos = {\n",
    "            mat[i][j]:(i,j) \n",
    "            for i in range(m) \n",
    "            for j in range(n) \n",
    "        }\n",
    "        for k,v in enumerate(arr):\n",
    "            i,j = v2pos[v]\n",
    "            mlefts[i]-=1\n",
    "            nlefts[j]-=1\n",
    "            if mlefts[i]==0 or nlefts[j]==0:\n",
    "                return k"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        book = {mat[i][j]: (i, j) for i, j in product(range(m), range(n))}\n",
    "        rows, cols = [0] * m, [0] * n\n",
    "        for i, (x, y) in enumerate(map(book.__getitem__, arr)):\n",
    "            rows[x] += 1\n",
    "            cols[y] += 1\n",
    "            if rows[x] == n or cols[y] == m:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, a: List[int], b: List[List[int]]) -> int:\n",
    "        m,n=len(b),len(b[0])\n",
    "        r=[0]*m\n",
    "        c=[0]*n\n",
    "        h={}\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                h[b[i][j]]=[i,j]\n",
    "        for j,i in enumerate(a):\n",
    "            x,y=h[i]\n",
    "            r[x]+=1\n",
    "            c[y]+=1\n",
    "            if r[x]==n or c[y]==m:\n",
    "                return j\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        n, m = len(mat), len(mat[0])\n",
    "        mp = {}\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                mp[mat[i][j]] = [i, j]\n",
    "        rowCnt, colCnt = [0] * n, [0] * m\n",
    "        for i in range(len(arr)):\n",
    "            v = mp[arr[i]]\n",
    "            rowCnt[v[0]] += 1\n",
    "            if rowCnt[v[0]] == m:\n",
    "                return i\n",
    "            colCnt[v[1]] += 1\n",
    "            if colCnt[v[1]] == n:\n",
    "                return i\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        n = len(mat[0])\n",
    "        m = len(mat)\n",
    "        num_index = dict()\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                num_index[mat[i][j]] = [i,j]\n",
    "        num_raw = [n]*m\n",
    "        num_col = [m]*n\n",
    "        for i in range(0,m*n):\n",
    "            num_raw[num_index[arr[i]][0]] -=1\n",
    "            num_col[num_index[arr[i]][1]] -=1\n",
    "            if num_raw[num_index[arr[i]][0]]==0 or num_col[num_index[arr[i]][1]]==0:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        dicrow={}\n",
    "        diccol={}\n",
    "        m=len(mat)\n",
    "        n=len(mat[0])\n",
    "        dic={}\n",
    "        for mm in range(m):\n",
    "            for nn in range(n):\n",
    "                dic[mat[mm][nn]]=[mm,nn]\n",
    "        \n",
    "        for i in range(len(arr)):\n",
    "            a=arr[i]\n",
    "            row,col=dic[a]\n",
    "            dicrow[row]=dicrow.get(row,0)+1\n",
    "            diccol[col]=diccol.get(col,0)+1\n",
    "            #print(dicrow,diccol,row,col,m,n)\n",
    "            if dicrow[row]==n or diccol[col]==m:\n",
    "                #print(dicrow,diccol)\n",
    "                return i\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:       \n",
    "        m, n = len(mat), len(mat[0])\n",
    "        hmap = defaultdict(list)  # {num: [rowNum, colNum]} 每个数字对应所属的行与列编号\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                hmap[mat[i][j]] = [i,j]\n",
    "        \n",
    "        r = [0] * m  # r[i] 第i行出现的数字个数\n",
    "        c = [0] * n  # c[i] 第i列出现的数字个数\n",
    "        for i, num in enumerate(arr):\n",
    "            rowNum, colNum = hmap[num]\n",
    "            r[rowNum] += 1\n",
    "            c[colNum] += 1\n",
    "            if r[rowNum] == n or c[colNum] == m:\n",
    "                return i\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        a_dict = {}\n",
    "        for i in range(len(mat)):\n",
    "            for j in range(len(mat[i])):\n",
    "                a_dict[mat[i][j]] = [i, j]\n",
    "        b_dict = {}\n",
    "        for i in arr:\n",
    "            col,line = a_dict[i]\n",
    "            if col not in b_dict:\n",
    "                b_dict[col] = 1\n",
    "            else:\n",
    "                b_dict[col] += 1\n",
    "            if b_dict[col] == n:\n",
    "                return arr.index(i)\n",
    "            if m + line not in b_dict:\n",
    "                b_dict[m+line] = 1\n",
    "            else:\n",
    "                b_dict[m+line] += 1\n",
    "            if b_dict[m+line] == m:\n",
    "                return arr.index(i)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m, n = len(mat), len(mat[0])\n",
    "        row = [0] * m\n",
    "        col = [0] * n \n",
    "        mp = defaultdict(int)\n",
    "        for i, x in enumerate(mat):\n",
    "            for j, val in enumerate(x):\n",
    "                mp[val] = [i,j]\n",
    "        for i, x in enumerate(arr):\n",
    "            a, b = mp[x][0], mp[x][1]\n",
    "            row[a] += 1\n",
    "            col[b] += 1\n",
    "            if row[a] == n or col[b] == m:\n",
    "                return i \n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        match = {}\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                match[mat[i][j]] = [i,j]\n",
    "        r = [0] * m\n",
    "        c = [0] * n\n",
    "        for i in range(m * n):\n",
    "            curr = match[arr[i]]\n",
    "            r[curr[0]] += 1\n",
    "            c[curr[1]] += 1\n",
    "            if r[curr[0]] == n or c[curr[1]] == m:\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m = len(mat)\n",
    "        n = len(mat[0])\n",
    "        row = [0] * m\n",
    "        col = [0] * n\n",
    "        mp = defaultdict(list)\n",
    "        for i,x in enumerate(mat):\n",
    "            for j,val in enumerate(x):\n",
    "                mp[val] = [i,j]\n",
    "        for i,x in enumerate(arr):\n",
    "            a = mp[x][0]\n",
    "            b = mp[x][1]\n",
    "            row[a] += 1\n",
    "            col[b] += 1\n",
    "            if row[a] == n or col[b] == m:\n",
    "                return i\n",
    "        return 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        m=len(mat)\n",
    "        n=len(mat[0])\n",
    "        #标记\n",
    "        row=[0]*m\n",
    "        col=[0]*n\n",
    "        #预记录\n",
    "        s=defaultdict(list)\n",
    "        for i,f in enumerate(mat) :\n",
    "            for j,x in enumerate(f) :\n",
    "                s[x]=[i,j]\n",
    "        for i,x in enumerate(arr) :\n",
    "            a,b=s[x][0],s[x][1]\n",
    "            row[a]+=1\n",
    "            col[b]+=1\n",
    "            if row[a]==n or col[b]==m :\n",
    "                return i\n",
    "        return 0\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:\n",
    "        M, N = len(mat), len(mat[0])\n",
    "        rc, cc = Counter(), Counter()\n",
    "        sarr = set(arr)\n",
    "        midx = {}\n",
    "        for i, row in enumerate(mat):\n",
    "            for j, cell in enumerate(row):\n",
    "                if cell in sarr:\n",
    "                    #rc[i] += 1\n",
    "                    #cc[j] += 1\n",
    "                    midx[cell] = (i, j)\n",
    "        \n",
    "        for i, n in enumerate(arr):\n",
    "            x, y = midx[n]\n",
    "            rc[x] += 1\n",
    "            cc[y] += 1\n",
    "            if rc[x] == N or cc[y] == M:\n",
    "                return i\n",
    "        \n",
    "        \n",
    "\n",
    "            \n",
    "        \n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
